The present invention relates to a curve generator and, more particularly, to a curve generator which generates a free curve from a group of given control points in a graphic display which outputs characters or graphic figures to a CRT or a printer.
As for a typical graphics related apparatus which deals with characters or graphics, there have existed personal computers and EWS (Engineer Work Stations), and these have been widely used. Graphics which can be generally used in these apparatuses are based on straight lines or circular arcs, and complicated graphics are expressed by a combination of these. In such apparatus, therefore, hardware which can draw a straight line and a circular arc is included in order to improve performance thereof. However, there exist graphics, other than the straight line and the circular arc, which are also used frequently. One of them is a free curve, and the free curves called a Bezier curve and a Spline curve are frequently used. Each of these free curves can express a smooth curve and, therefore, is not only useful for CAD (Computer Aided Design) which can design various kinds of products with a computer but also is available for character expression named "outline font" which has been recently paid much attention.
The outline font means that a character is defined with coordinate values of terminal points on line segments which outline the character. In order to display or print the character, an inside area of the outline thereof is filled in. The outline of the character comprises a mixture of straight lines and curves. The curves are generally free curves rather than circular arcs. A curved portion of the outline can be approximated with short line segments, but this results in an extremely large number of line segments per character. The disadvantages therein are that the necessary information to define the character becomes huge and that, when the character is magnified, the quality thereof becomes poor because the curved portion thereof which is approximated with line segments appears as a group of straight lines. Therefore, a curve called a Bezier curve is generally employed for the outline font.
According to the Bezier curve method, when several control points are given, the smooth curve of a Bezier curve can be interpolated in the vicinity of the points. The curve frequently used is a 3rd-order Bezier curve. When four points are given as control points, the 3rd-order Bezier curve can not only be interpolated for the four points but also be an extremely smooth curve because, when a Bezier curve is newly drawn for four points consisting of one point newly given and three points out of the original four points excepting the start point thereof, the 1st- and 2nd-order differential coefficients of the first Bezier curve coincide with those of the second Bezier curve at a connecting point of both the curves. The free curve, as mentioned above, has the advantage in that the amount of information which defines a shape of the curve is small and in that, when the outline font of a character is magnified or reduced to be displayed or printed, the quality of the character does not deteriorate.
Next, an algorithm of generating Bezier curve will be explained. There has been generally known an algorithm which finds the curve by means of calculation from the start point thereof. In this case, however, the calculating speed is slow with a general purpose computer because numerous calculations of multiplication and division must be executed. Therefore, an algorithm which can be geometrically processed to find the curve is usually employed.
FIG. 1 is a coordinate diagram for the explanation of the geometrical algorithm which generates the 3rd-order Bezier curve. At first, of the arbitrary four points given as control points, middle points E, F and G of line segments Ab, BC and CD should be found. The middle point can be found with the calculation in which coordinate values of the control points on the line segment are added to each other and then, divided by two. Next, middle points H and I of line segments EF and FG should be found and then, a middle point J of a line segment HI should be found. This point J is on the 3rd-order Bezier curve. Next, when the process mentioned above is conducted for points A, E, H and J as control points, a next point Q on the curve is found. As explained above, after the point on the curve is found, the recursive process is repeatedly conducted for a new control point to find a next point on the curve.
When the process mentioned above is repeatedly conducted, the found point on the curve gradually and infinitely approaches the start point A. Therefore, it is necessary to stop the process when the found point substantially approaches the start point and to change the process in order to find a new point. In other words, when the distance between the point A and the found point Q on the curve, as shown in FIG. 1, is smaller than a predetermined value, the next control points should be J, I, G and D.
For generating the free curve mentioned above, there is a conventional apparatus in which, since it executes the process with software, the processing time is long. According to the conventional apparatus, it is necessary for a general purpose computer to execute the processes of several hundred clock pulses in order to find one point on the curve. In order to find an X coordinate value of a middle point, two-time loadings of data, one addition, one shifting (that is, division by two) and one storing need be processed. In order to find X coordinate values and Y coordinate values of 6 points, therefore, there are needed operations including at least 60 steps. In order to execute the instruction of one step, it takes 4 clock period because fetching the instruction, reading an operand, executing operation and storing its result are required. This results in the need of several hundred clock pulses to find one point on the curve. Moreover, there are needed the processes, for example, in which the distance between the control point and the point on the curve is calculated to be compared with the predetermined value, and in which data are exchanged when the distance is smaller than the predetermined value, so that the processing speed becomes slower.